import java.io.PrintWriter;

public class AutomatoFinito {

	// Esse e o alfabeto associado ao automato
	private Alfabeto alfabeto;
	// Guarda os estados que o automato possui, o primeiro
	// elemento e o estado inicial
	private Estado[] listaEstados;
	// Essa String armazena a saida que devera ser apresentada ao fim da
	// execucao
	private String saida = "";
	// Essa variavel armazena a quantidade inicial de estados
	private final int cardinalidadeEstadosInicial;

	// Com esse construtor inicializamos todas as variaveis da maquina, assim
	// como as transicoes de estado
	public AutomatoFinito(String[] dados) {

		this.setAlfabeto(dados[1]);
		this.setListaEstados(dados[0]);
		this.setTransicoes(dados[2]);
		this.cardinalidadeEstadosInicial = listaEstados.length;

	}

	// Esse e o metodo chamado para inicializar o funcionamento da maquina e
	// imprimir a saida
	public void rodar(String[] cadeias, PrintWriter gravarArq) {

		// Primeiramente imprimimos o automato
		// Ou seja, salvamos em saida
		imprimirAutomato();

		saida += "\r\n\r\n\r\n Analisando Cadeias";

		for (int i = 0; i < cadeias.length; i++) {

			saida += "\r\n\r\n  " + String.valueOf(i + 1) + " - \""
					+ cadeias[i] + "\"";
			checarCadeia(cadeias[i]);

		}

		gravarArq.printf(saida);

	}

	// Nesse metodo, o alfabeto e criado
	// O parametro dados passada e a segunda linha do arquivo de entrada
	private void setAlfabeto(String dados) {

		// Primeiramente precisamos definir a cardinalidade
		int pos = 0;
		while (dados.charAt(pos) != '"')
			pos++;
		int cardinalidade = Integer.valueOf(dados.substring(0, pos));
		// Removemos o trecho que continha a informacao da cardinalidade
		dados = dados.substring(pos);
		// Removemos as aspas
		dados = dados.replaceAll("\"", "");
		// Removemos as virgulas presentes em dados
		String[] dadosSeparados = dados.split(",");
		// Criamos o alfabeto
		alfabeto = new Alfabeto(cardinalidade, dadosSeparados);

	}

	// Esse metodo e responsavel por preencher a lista de estados deste automato
	// O parametro dados contem a primeira linha do arquivo de entrada
	private void setListaEstados(String dados) {

		// Primeiramente precisamos definir a cardinalidade
		int pos = 0;
		while (dados.charAt(pos) != '"')
			pos++;
		int cardinalidade = Integer.valueOf(dados.substring(0, pos));
		// Alocamos a memoria para a lista de estados
		listaEstados = new Estado[cardinalidade];
		// Removemos o trecho que continha a informacao da cardinalidade
		dados = dados.substring(pos);
		// Retiramos as aspas
		dados = dados.replaceAll("\"", "");
		// Separamos dados utilizando a virgula
		String[] dadosSeparados = new String[cardinalidade];
		dadosSeparados = dados.split(",");
		// Agora criamos os estados
		for (int i = 0; i < cardinalidade; i++) {

			boolean eFinal = false;
			// Checamos se o estado e final, ou seja, possui '*'
			if (dadosSeparados[i].charAt(0) == '*') {
				eFinal = true;
				dadosSeparados[i] = dadosSeparados[i].substring(1);
			}

			// Criamos um novo estado
			listaEstados[i] = new Estado(dadosSeparados[i], eFinal,
					alfabeto.getCardinalidade(), listaEstados.length);

		}

	}

	// Esse metodo e responsavel por definir as transicoes de estado
	// O parametro dados corresponde as ultimas linhas presentes no arquivo de
	// entrada
	private void setTransicoes(String dados) {

		// Retiramos as aspas
		dados = dados.replaceAll("\"", "");

		// Separamos os dados, levando em consideracao a virgula
		String[] dadosSeparados = dados.split(",");

		// Agora devemos buscar os estados presentes nas transicoes e
		// associa-los
		// Primeiramente para as transicoes diferentes de outros
		for (int i = 0; i < dadosSeparados.length; i = i + 3) {

			// Buscamos o estado de origem
			Estado origem = buscarEstado(dadosSeparados[i]);
			// Buscamos a posicao associado ao simbolo de entrada
			int posicao = alfabeto.buscarPosicao(dadosSeparados[i + 1]);
			// Buscamos o estado de destino
			Estado destino = buscarEstado(dadosSeparados[i + 2]);

			origem.associarTransicao(destino, posicao);

		}

		for (int i = 0; i < listaEstados.length; i++)
			listaEstados[i].ordenarTransicoes();

	}

	// Esse metodo e responsavel por buscar um estado pelo nome
	// Caso nao seja encontrado, informa ao usuario
	// Essa mensagem indica que ha um problema no arquivo de entrada
	private Estado buscarEstado(String nome) {

		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i].getNome().equals(nome))
				return listaEstados[i];

		// Essa mensagem e enviada quando ha alguma inconsitencia no arquivo de
		// entrada
		System.err.println("Estado nao encontrado");
		System.exit(1);
		return null;

	}

	// Esse metodo informa se ainda ha transicoes em vazio no automato
	// Devolve true em caso afirmativo
	private boolean verificarTransicaoVazio() {

		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i].verificarTransicaoVazio())
				return true;

		return false;

	}

	// Esse metodo remove todas as transicoes em vazio do automato realizando
	// merge de linhas
	private void removerTransicoesVazio() {

		while (verificarTransicaoVazio()) {

			for (int i = 0; i < listaEstados.length; i++) {

				Estado[] prov = listaEstados[i].getTransicoesVazio();

				// Verificamos se existe pelo menos uma transicao em vazio
				if (prov[0] == null) {
					// Nao fazemos nada
				} else {

					// Verificamos se algum dos estados que ocorrera merge e
					// final
					boolean eFinal = false;

					for (int j = 0; j < prov.length; j++)
						if (prov[j] != null)
							if (prov[j].verificarFinal())
								eFinal = true;

					if (eFinal)
						listaEstados[i].setFinal();

					// Nesse laco fazemos o merge de estados
					for (int j = 0; j < prov.length; j++)
						if (prov[j] != null)
							listaEstados[i].juntarEstado(prov[j]);

					// Agora precisamos remover os estados que realizamos o
					// merge
					for (int j = 0; j < prov.length; j++)
						if (prov[j] != null)
							listaEstados[i].removerEstadoTransicaoVazio(prov[j]
									.getID());

				}

			}

		}

	}

	// Esse metodo lista os estados da maquina, informando se sao iniciais e/ou
	// finais
	private String imprimirListaEstados() {

		String prov = "";

		for (int i = 0; i < listaEstados.length; i++) {

			prov += "\r\n   " + String.valueOf(listaEstados[i].getID() + 1)
					+ ") ";
			prov += listaEstados[i].getNome();
			if (i == 0) // Estado inicial
				prov += "  (Inicial)";
			if (listaEstados[i].verificarFinal()) // Estado final
				prov += "  (Aceitacao)";

		}

		return prov;

	}

	// Esse metodo imprime o automato
	// Caso esse autonomo nao seja deterministico, esse metodo o transforma em
	// um, informando
	private void imprimirAutomato() {

		saida = "Automato Finito\r\n\r\n  Os estados desta maquina sao:";

		saida += imprimirListaEstados();

		saida += "\r\n\r\n  Temos a seguinte tabela de transicoes:";

		saida += imprimirTabelaTransicao();

		if (verificarDeterminismo()) {

			saida += "\r\n  O automato informado e deterministico.";

		} else {

			removerNaoDeterminismos();

			saida += "\r\n  O automato informado nao e deterministico.";

			saida += "\r\n\r\n  Transformando este automato em deterministico, temos:";

			saida += "\r\n\r\n  Apos remover as transicoes em vazio, as transicoes "
					+ "multiplas com um mesmo simbolo e os estados inatingiveis, "
					+ "temos a seguinte lista de estados (\"@\": Vazio):";

			saida += imprimirListaEstados();

			saida += "\r\n\r\n  Com isso temos a seguinte tabela de transicoes:";

			saida += imprimirTabelaTransicao();

		}

	}

	private boolean verificarDeterminismo() {

		if (verificarTransicaoVazio())
			return false;

		if (verificarMultiplasTransicoes())
			return false;

		return true;

	}

	// Esse metodo verifica se existem multiplas transicoes no automato
	private boolean verificarMultiplasTransicoes() {

		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i].verificarMultiplasTransicoes())
				return true;

		return false;

	}

	// Esse metodo e responsavel por remover os nao determinismos presentes no
	// automato
	private void removerNaoDeterminismos() {

		removerTransicoesVazio();

		removerMultiplasTransicoes();

		definirEstadosInatingiveis();

		removerEstadosInatingiveis();

	}

	// Esse metodo e responsavel por remover as multiplas transicoes presentes
	// no automato. Isto e feito criando-se novos estados na maquina
	private void removerMultiplasTransicoes() {

		while (verificarMultiplasTransicoes()) {

			boolean encontrou = false;
			Estado[] prov;
			String nomeEstado = "";
			boolean eFinal = false;

			// Precisamos encontrar a primeira ocorrencia de multiplas
			// transicoes
			for (int i = 0; i < listaEstados.length && !encontrou; i++)
				if (listaEstados[i].verificarMultiplasTransicoes()) {

					encontrou = true;

					prov = listaEstados[i].getMultiplasTransicoes();

					// Armazenamos a concatenacao dos nomes
					for (int j = 0; j < prov.length; j++)
						nomeEstado += prov[j].getNome() + ",";

					for (int j = 0; j < prov.length; j++)
						if (prov[j].verificarFinal())
							eFinal = true;

				}

			// Removemos o ultimo sinal de , presente em nomeEstado
			nomeEstado = nomeEstado.substring(0, nomeEstado.length() - 1);

			// Criamos o novo estado
			Estado novo = new Estado(nomeEstado, eFinal,
					alfabeto.getCardinalidade(), cardinalidadeEstadosInicial);

			// Precisamos definir as transicoes deste novo estado
			// Para isso, realizamos o merge das linhas que foram juntas
			String[] nomes = nomeEstado.split(",");
			for (int i = 0; i < nomes.length; i++) {

				Estado prov2 = buscarEstado(nomes[i]);

				novo.juntarEstado(prov2);

			}

			for (int i = 0; i < listaEstados.length; i++)
				listaEstados[i].removerMultiplasTransicoes(novo);

			inserirEstado(novo);

		}

	}

	// Esse metodo e responsavel por adicionar um nomo estado em listaEstado
	private void inserirEstado(Estado novo) {

		Estado[] prov = new Estado[listaEstados.length + 1];

		for (int i = 0; i < listaEstados.length; i++)
			prov[i] = listaEstados[i];

		prov[listaEstados.length] = novo;

		listaEstados = prov;

	}

	// Esse metodo e responsavel por marcar os estados inatingiveis
	private void definirEstadosInatingiveis() {

		for (int k = 0; k < 2; k++)
			for (int i = 1; i < listaEstados.length; i++) {

				boolean atingivel = false;
				String nome = listaEstados[i].getNome();

				for (int j = 0; j < listaEstados.length; j++)
					if (listaEstados[j] != null)
						if (i != j && listaEstados[j].verificarAtingivel())
							if (listaEstados[j].verificarTransicao(nome))
								atingivel = true;

				if (!atingivel)
					listaEstados[i].setInatingivel();

			}

	}

	// Esse metodo e responsavel por remover os estados inatingiveis
	private void removerEstadosInatingiveis() {

		int cont = 0;

		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i].verificarAtingivel())
				cont++;

		Estado.resetarGeradorID();

		Estado[] prov = new Estado[cont];

		int pos = 0;

		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i].verificarAtingivel())
				prov[pos++] = new Estado(listaEstados[i].getNome(),
						listaEstados[i].verificarFinal(),
						listaEstados[i].getTransicoes());

		listaEstados = prov;

		atualizarID();

	}

	// Atualiza os id das transicoes de estado
	private void atualizarID() {

		for (int i = 0; i < listaEstados.length; i++)
			for (int j = 0; j < listaEstados.length; j++)
				listaEstados[i].atualizarIDTransicoes(
						listaEstados[j].getNome(), listaEstados[j].getID());

	}

	// Esse metodo e responsavel por analisar a cadeia e gerar seu caminho no
	// autonomo
	private void checarCadeia(String cadeia) {

		// Armazena o estado corrente
		Estado atual = listaEstados[0];

		// Armazena a iteracao
		int cont = 1;

		// Informa se devemos continuar ou nao
		boolean continuar = true;

		// Devemos checar a cadeia inteira
		while (!cadeia.equals("") && continuar) {

			// Devemos pegar o primeiro simbolo da cadeia
			String simboloAtual = "";
			simboloAtual = cadeia.substring(0, 1);

			// Quando encontrarmos um simbolo presente no alfabeto, armazenamos
			// nesta variavel
			String simboloValido = "";

			// Essa variavel e utiizada para marcarmos a posicao na cadeia
			int pos = 1;

			boolean acabouCadeia = false;

			while (alfabeto.verificarSubcadeia(simboloAtual)
					&& pos <= cadeia.length() + 1 && !acabouCadeia) {

				if (alfabeto.verificarSimbolo(simboloAtual))
					simboloValido = simboloAtual;

				if (pos == cadeia.length() + 1)
					acabouCadeia = true;
				else
					simboloAtual = cadeia.substring(0, pos++);

			}

			// Caso nao encontremos um simbolo no alfabeto, pegamos o proximo
			// simboloo na cadeia com a expectativa de uma transicao em outros
			if (simboloValido.equals(""))
				simboloValido = cadeia.substring(0, 1);

			saida += "\r\n   " + String.valueOf(cont++) + ") ";

			saida += atual.getNome() + "  = " + simboloValido + " => ";

			// Buscamos o proximo estado
			// Caso nao encontremos uma transicao com o simbolo, tentamos com
			// transicao outros
			if (atual.getProximoEstado(alfabeto.buscarPosicao(simboloValido)) == null)
				atual = atual.getProximoEstado(alfabeto.getCardinalidade());
			else
				atual = atual.getProximoEstado(alfabeto
						.buscarPosicao(simboloValido));

			if (atual != null)
				saida += atual.getNome();
			else {

				saida += " X (Falhou: transicao inexistente)";

				continuar = false;

			}

			// Precisamos atualizar a cadeia
			cadeia = cadeia.substring(simboloValido.length());

		}

		if (atual == null)
			saida += "\r\n\r\n    A cadeia nao e aceita pelo autonomo finito, pois ocorreu uma falha.";

		else {

			if (atual.verificarFinal())
				saida += "\r\n\r\n    A cadeia e aceita pelo autonomo finito.";

			else
				saida += "\r\n\r\n    A cadeia nao e aceita pelo autonomo finito, pois o estado final nao e de aceitacao.";

		}

	}

	// Esse metodo e responsavel por imprimir a tabela de transicoes quando o
	// automato e deterministico ou nao deterministico
	private String imprimirTabelaTransicao() {

		int tamanho = alfabeto.getCardinalidade() + 2;

		if (!verificarDeterminismo())
			tamanho++;

		String prov = "";

		// Essa variavel armazena o tamanho da maior string de cada coluna da
		// tabela
		int[] maiorNomeTamanho = new int[tamanho];

		// Para a primeira coluna (estados), temos
		for (int i = 0; i < listaEstados.length; i++)
			if (listaEstados[i] != null)
				if (maiorNomeTamanho[0] < (String.valueOf(
						listaEstados[i].getID()).length() + 2 + listaEstados[i]
						.getNome().length()))
					maiorNomeTamanho[0] = String.valueOf(
							listaEstados[i].getID()).length()
							+ 2 + listaEstados[i].getNome().length();

		// Para as demais colunas, devemos inicializar os valores iniciais
		for (int i = 0; i <= tamanho - 2; i++)
			maiorNomeTamanho[i + 1] = alfabeto.getSimbolo(i).length() + 2;

		// Agora comparamos e atualizamos
		for (int i = 0; i <= tamanho - 2; i++)
			for (int j = 0; j < listaEstados.length; j++)
				if (listaEstados[j].getProximoEstado(i) != null)
					if (maiorNomeTamanho[i + 1] < String.valueOf(
							listaEstados[j].getProximoEstado(i).getID())
							.length())
						maiorNomeTamanho[i + 1] = String.valueOf(
								listaEstados[j].getProximoEstado(i).getID())
								.length();

		// Precisamos colocar o offset
		prov += "\r\n    ";

		// Primeira linha
		for (int i = 0; i < maiorNomeTamanho[0]; i++)
			prov += " ";

		for (int i = 0; i <= tamanho - 2; i++) {
			prov += "|";

			for (int j = 0; j < (maiorNomeTamanho[i + 1] - alfabeto.getSimbolo(
					i).length()) / 2; j++)
				prov += " ";

			prov += "\"" + alfabeto.getSimbolo(i) + "\"";

			for (int j = 0; j < (maiorNomeTamanho[i + 1] - alfabeto.getSimbolo(
					i).length())
					- (maiorNomeTamanho[i + 1] - alfabeto.getSimbolo(i)
							.length()) / 2; j++)
				prov += " ";

		}

		prov += "|\r\n";

		// Demais linhas
		for (int i = 0; i < listaEstados.length; i++) {

			prov += "    " + String.valueOf(listaEstados[i].getID()) + ") ";

			prov += listaEstados[i].getNome();

			for (int j = 0; j < maiorNomeTamanho[0]
					- listaEstados[i].getNome().length()
					- String.valueOf(listaEstados[i].getID()).length() - 2; j++)
				prov += " ";

			for (int j = 0; j <= tamanho - 2; j++) {

				prov += "| ";

				if (listaEstados[i].getProximoEstado(j) != null) {
					for (int k = 0; k < (maiorNomeTamanho[j + 1] - String
							.valueOf(
									listaEstados[i].getProximoEstado(j).getID())
							.length()) / 2; k++)
						prov += " ";

					prov += String.valueOf(listaEstados[i].getProximoEstado(j)
							.getID());

					for (int k = 0; k < (maiorNomeTamanho[j + 1] - String
							.valueOf(
									listaEstados[i].getProximoEstado(j).getID())
							.length())
							- (maiorNomeTamanho[j + 1] - String
									.valueOf(
											listaEstados[i].getProximoEstado(j)
													.getID()).length()) / 2; k++)
						prov += " ";
				}

				else
					for (int k = 0; k < maiorNomeTamanho[j + 1]; k++)
						prov += " ";

				prov += " ";
			}

			prov += "|\r\n";

		}

		return prov;

	}

}